package a.codetop;

import org.junit.Test;

/*
找单元格中的所有的门，然后从每个门的上下左右4个方向出发，去搜索所有单元格，把能覆盖到的单元格赋值。
遇到3种情况停止搜索：1.墙，-1；2.新的门，0；3.其他门能通到这里且距离比当前距离小
 */
public class _21力扣的迷宫题_不好太难_286_用板子改写下 {

//1起点2147483647
//2终点0
//0可走2147483647
//-1障碍-1
//6走过6
    int[][] g;
    int[][] fx = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public void wallsAndGates(int[][] g) {
        this.g = g;
        //找起点
        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < g[0].length; j++) {
                if (g[i][j] == 0) {
                    //前序深搜
                    qian(i, j);
                }
            }
        }
    }
    int step = 0;
    void qian(int i, int j) {
        for (int k = 0; k < fx.length; k++) {
            int x = i + fx[k][0], y = j + fx[k][1];
            //停止
            if (x < 0 || x >= g.length || y < 0 || y >= g[0].length //越界
                    || g[x][y] == -1 //墙
                    || g[x][y] == 0  //其他门
                    || g[x][y] < step //其他门更近
            ) continue;
            //走
            step++;
            g[x][y] = Math.min(g[x][y], step);
            qian(x, y);
            step--;
        }
    }
}
